Chặn Chernoff

Trong lý thuyết xác suất, chặn Chernoff, đặt tên theo Herman Chernoff, cho một chặn trên giảm theo hàm mũ của đuôi phân phối của tổng nhiều biến ngẫu nhiên độc lập. Nó thường mạnh hơn các bất đẳng thức sử dụng mômen bậc nhất hay bậc hai chẳng hạn như bất đẳng thức Markov hay bất đẳng thức Chebyshev.Nó có liên hệ với bất đẳng thức Bernstein, và bất đẳng thức Hoeffding.Sau đây là một ví dụ trường hợp đặc biệt của chặn Chernoff. Giả sử X1,..., Xn là các biến ngẫu nhiên Bernoulli độc lập với xác suất p > 1/2. Khi đó, nếu gọi xác suất xảy ra ít nhất n/2 sự kiện { X k = 1 } {\displaystyle \{X_{k}=1\}} là P, thìChặn Chernoff cho thấy P có chặn dưới như sau:Dưới đây, trường hợp này sẽ được tổng quát hóa theo nhiều hướng khác nhau. Có nhiều phiên bản khác nhau của chặn Chernoff: sai số có thể là sai số tuyệt đối hoặc sai số tương đối so với giá trị kỳ vọng.